#include "main.h"
// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
    void _create_tree(BiTreeNode * root_pp, char * pre_order_seq, int *current_index, int num_elements) {
        if (*current_index >= num_elements){
            return;
        } else {
            root_pp->data = pre_order_seq[*current_index];
            *current_index += 1;
        }
        if (pre_order_seq[*current_index] == '#') {
            root_pp->leftChild = NULL;
            *current_index += 1;
        } else {
            root_pp->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            _create_tree(root_pp->leftChild, pre_order_seq, current_index, num_elements);
        }
        if (pre_order_seq[*current_index] == '#') {
            root_pp->rightChild = NULL;
            *current_index += 1;
        } else {
            root_pp->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            _create_tree(root_pp->rightChild, pre_order_seq, current_index, num_elements);
        }
    }


        void create_tree(BiTreeNode **root_pp, char *pre_order_seq, int num_elements) {
            *root_pp = (BiTreeNode *) malloc(sizeof(BiTreeNode));
            BiTreeNode *root = *root_pp;
            if (pre_order_seq[0] != '#') {
                root->data = pre_order_seq[0];
            }
            int current_index = 0;
            _create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
        }

//使用visit(item)函数前序遍历二叉树t
        void pre_order_traverse(BiTreeNode *t, void visit(DataType item)) {
            if (t != NULL) {
                visit(t->data);
                pre_order_traverse(t->leftChild, visit);
                pre_order_traverse(t->rightChild, visit);
            }
        }

//使用visit(item)函数中序遍历二叉树t
        void in_order_traverse(BiTreeNode *t, void visit(DataType item)) {
            if (t == NULL) {
                return;
            }
            in_order_traverse(t->leftChild, visit);
            visit(t->data);
            in_order_traverse(t->rightChild, visit);
        }

//使用void visit(DateType item)函数后序遍历二叉树t
        void post_order_traverse(BiTreeNode *t, void visit(DataType item)) {
            if (t == NULL) {
                return;
            }
            post_order_traverse(t->leftChild, visit);
            post_order_traverse(t->rightChild, visit);
            visit(t->data);
        }

// 可以无需更改本函数的实现
        void visit(DataType item) {
            printf("%c ", item);
        }

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
        BiTreeNode *search(BiTreeNode *root, DataType x) {
            BiTreeNode *find = NULL;
            if (root == NULL) {
                return NULL;
            }
            if (root->data == x) {
                return root;
            } else {
                find = search(root->leftChild, x);
                if (find) {
                    return find;
                }
                find = search(root->rightChild, x);
                if (find) {
                    return find;
                }
            }
            return find;
        }

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
        void destroy(BiTreeNode **root) {
            if ((*root) != NULL) {
                if ((*root)->leftChild) {
                    destroy(&(*root)->leftChild);
                    (*root)->leftChild = NULL;
                }
                if ((*root)->rightChild) {
                    destroy(&(*root)->rightChild);
                    (*root)->rightChild = NULL;
                }
                if ((*root) != NULL) {
                    free((*root));
                    (*root) = NULL;
                }
            }
        }

//
        int main() {
            BiTreeNode *root;
            char x='A';
            char *pre_order_seq = "ABC##DE#G##F###";
            create_tree(&root, pre_order_seq, 15);
            printf("前序遍历为：");
            pre_order_traverse(root, visit);
            printf("\n中序遍历为：");
            in_order_traverse(root,visit);
            printf("\n后序遍历为：");
            post_order_traverse(root,visit);
            search(root,x);
            printf("\n数据元素%c在二叉树中 \n",x);
            destroy(&root);
        }	
